Genetic algorithms provide a technique for solving optimization problems that are based on natural selection, the process that drives biological evolution. The optimization problem being solved may include linear constraints and boundary constraints as well as non-linear constraints. A genetic algorithm repeatedly modifies a population of individual solutions in order to create a new population. At each generation, the genetic algorithm selects individuals from the current population to be parents and uses the selected individuals to produce the children for the next generation. Over successive generations, the population “evolves” toward an “optimal solution.
A genetic algorithm uses three main types of operations to create the next population from the current population, namely elites, crossover, and mutation. Elites are individuals selected intact from the current population. Crossover is a technique to swap content from individuals in the current population to create new individuals for the next generation. The third type of operation, the mutation operation is of special interest for the current discussion and is discussed in detail below.
In a genetic algorithm, a mutation operator is a genetic operator used to maintain diversity in a population from one generation to the next. An example of a mutation operator involves the probability that some arbitrary element in a point vector (individual) will be changed from its original state. FIG. 1 illustrates a mutation example in which two elements are randomly chosen and changed to a random value. A point vector A (10) includes elements 11, 12, 13, 14 and 15. A second point vector B (20) is also shown where B is an example of an individual selected by mutating selected elements within point vector A. Point vector B (20) includes elements 21, 22, 23, 24 and 25. Element 11 was mutated into element 21 and Element 15 was mutated into element 25. The values of elements 12, 13 and 14 is the same of that of respective elements 22, 23 and 24. The mutating of the individuals helps prevent premature convergence in the overall population.
FIG. 2 illustrates in a graph 30 the effect of a mutation operation in a conventional unconstrained optimization problem. An individual P2 (34) is generated via a mutation operation on current individual P1 (32) in an unconstrained optimization problem.
One of the difficulties with existing mutation algorithms, such as uniform random mutation and Gaussian mutation, is that while they are very useful in unconstrained optimization, it is very difficult to perform a mutation step in a constrained optimization while maintaining feasibility (a feasible individual represents an acceptable possible solution to the problem being optimized taking into consideration the applicable constraints). For example, in FIG. 3 a graph 40 depicts two linear constraints 46 and 48 and a point P1 (42). Conventional mutation operators that do not take into account the linear constraints 46 and 48 may generate an individual P2 (44) that is located outside the feasible region 50 and therefore not usable as a possible solution to the optimization problem.
A conventional technique for dealing with the generation of solutions to an optimization problem with constraints is to use a penalty method to account for the constraints. A discussion of a common use of the penalty method in optimization problems with linear, bound, and non-linear constraints follows below.
The optimization problem being solved may be represented as:
      Minimize    x    ⁢          ⁢      f    ⁡          (      x      )                      Such thatCi(x)≦0,i=1 . . . m Ci(x)=0,i=m+1 . . . mt Ax≦bAeqx=beq LB≦x≦UB  (A)where the Ci(x) are nonlinear inequality and equality constraints. The integer “m” is the number of nonlinear inequality constraints and mt is the total number of nonlinear constraints. Ax≦b and Aeqx=beq are linear constraints, LB and UB are lower and upper bounds on the decision variable x.        
The most popular approach to perform optimization, subject to constraints, is to formulate a sub-problem with a penalty parameter, and then solve the sub-problem. The sub-problem formulated from the original problem (A) is shown below:
      Θ    ⁡          (              x        ,        ρ            )        =            f      ⁡              (        x        )              -          ρ      ⁡              (                                            ∑                              i                =                1                            m                        ⁢                                                  ⁢                          max              ⁡                              (                                  0                  ,                                      Ax                    -                    b                                                  )                                              +                                    ∑                              i                =                                  m                  +                  1                                            mt                        ⁢                                                  ⁢                                                                                              A                    eq                                    ⁢                  x                                -                                  b                  eq                                                                            +                                    ∑                              i                =                1                            m                        ⁢                                                  ⁢                          max              ⁡                              (                                  0                  ,                                                            c                      i                                        ⁡                                          (                      x                      )                                                                      )                                              +                                    ∑                              i                =                                  m                  +                  1                                            mt                        ⁢                                                  ⁢                                                                          c                  i                                ⁡                                  (                  x                  )                                                                                  )            This sub-problem is solved using a fixed value for ρ or by making ρ dependent on the generation number. Both the linear and the nonlinear constraints are included in the sub-problem, and this is solved subject to the bounds. Bounds are satisfied by choosing appropriate mutation and crossover operators. It should be noted that the linear constraints are included as part of the sub-problem.
Unfortunately, these conventional algorithms suffer from a number of drawbacks when it comes to constrained optimization problems. A difficult aspect of this approach is that it requires a user to choose the right value of ρ for different problems. Additionally, the combination of the linear and nonlinear constraints makes the sub-problem difficult to solve. The linear and bound constraints provide much information that is not used to solve the problem. Also, guessing a value of the penalty parameter ρ is not trivial and often requires some experimentation. If a dynamic penalty parameter is used, there is no adequate way to update this parameter. This type of conventional algorithm to handle constrained optimization also does not scale well as it is inefficient for larger problems that have more decision variables and constraints.